// 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

// 例如，给出 n = 3，生成结果为：

// [
//   "((()))",
//   "(()())",
//   "(())()",
//   "()(())",
//   "()()()"
// ]

#include <vector>
#include <string>

using namespace std;

/* 回溯
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
时间复杂度：O()
空间复杂度：O()
*/
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res{};
        generateParenthesis(n, n, "", res);
        return res;
    }
private:
    void generateParenthesis(int left, int right, string s, vector<string>& res) {
        if (left == 0 && right == 0) {
            res.push_back(s);
            return;
        }
        如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
        if (left > 0) {
            generateParenthesis(left-1, right, s + "(", res);
        }
        if (left < right) {
            generateParenthesis(left, right-1, s + ")", res);
        }
    }
};

/* 回溯
时间复杂度：O()
空间复杂度：O()
*/
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res{};
        string s{};
        backtrace(res, s, 0, 0, n);
        return res;
    }
    void backtrace(vector<string>& res, string& s, int left, int right, const int& n) {
        if (s.size() == n*2) {
            res.push_back(s);
            return;
        }
        if (left < n) {
            s += "(";
            backtrace(res, s, left + 1, right, n);
            s.pop_back();
        }
        if (right < left) {
            s += ")";
            backtrace(res, s, left, right + 1, n);
            s.pop_back();
        }
    }
};

/* 按括号序列的长度递归
每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
时间复杂度：O()
空间复杂度：O()
*/
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        return *generate(n);
    }
private:
    shared_ptr<vector<string>> cache[100] = {nullptr};
    shared_ptr<vector<string>> generate(int n) {
        if (cache[n] != nullptr) {
            return cache[n];
        }
        if (n == 0) {
            cache[0] = shared_ptr<vector<string>>(new vector<string>{""});
        } else {
            auto res = shared_ptr<vector<string>>(new vector<string>{});
            for (int i{0}; i != n; ++i) {
                auto lefts = generate(i);
                auto rights = generate(n - i - 1);
                for (const string& left : *lefts) {
                    for (const string& right : *rights) {
                        res->push_back("(" + left + ")" + right); // (a)b
                    }
                }
            }
            cache[n] = res;
        }
        return cache[n];
    }
};
